package graph.disJointSet;

/**
 * 2021/10/06
 * 引出并查集，为了解决图里面节点成环的问题。
 * V1：在图里面，如果二个顶点连通，我们维护一个parent数组，下标i对应顶点的下标，下标i对应的值表示i顶点父节点在数组中位置
 * 比如 :  A->B,A->C  C和B的父节点为A
 * arr = {-1,0,0}
 * V2：但是！ 上面那种情况还是会有树退化的情况 我们提出V3进行一个树高度的处理 用一个数组存储xRoot 节点与yRoot节点的高度
 */
public class DisJointSet {
    public static void main(String[] args) {
        int[][] edges = new int[][]{
                {0, 1}, {1, 2}, {1, 3},
                {2, 4}, {3, 4}, {2, 5}
        };
        VERTICES = edges.length;  // 表示有多少个顶点
        int[] parent = new int[VERTICES];   // i表示节点，parent[i]表示父节点位置
        int[] rank = new int[VERTICES];  // 默认为0  root高度数组
        initialise(parent);
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];  //起点
            int y = edges[i][1];   //终点
            if (unionVertices(x, y, parent, rank) == false) {
                System.out.println("Circle detected" + x + "," + y);
            }
        }

    }
    public static int VERTICES; // 6个顶点
    /**
     * 初始化 默认为-1
     * @param parent
     */
    static void initialise(int parent[]) {
        for (int i = 0; i < VERTICES; i++) {
            parent[i] = -1;
        }
    }

    /**
     * 寻找x的root节点，循环找。如果x没有父节点返回自己。
     */
    static int findRoot(int x, int[] parent) {
        while (parent[x] != -1) {
            x = parent[x];
        }
        return x;
    }

    /**
     * 并集的操作  Version1 x无脑成为y的儿子。 会导致树的退化
     */
    static boolean unionVertices(int x, int y, int[] parent) {
        int xRoot = findRoot(x, parent);
        int yRoot = findRoot(y, parent);
        if (xRoot == yRoot) {
            return false;
        } else {
            parent[xRoot] = yRoot;
        }
        return true;
    }

    /**
     * 连接的操作 Version2  维护一个rank数组，里面保存的是根节点的高度
     * 最初 0 与 1 相连的情况，二棵树高度都为0，x成为1的子孙，1树高度++。
     * rank数组真的太精妙了
     */
    static boolean unionVertices(int x, int y, int[] parent, int[] rank) {
        int xRoot = findRoot(x, parent);
        int yRoot = findRoot(y, parent);
        if (xRoot == yRoot) {
            return false;
        } else {
            if (rank[x] > rank[y]) {
                parent[yRoot] = xRoot;
            } else if (rank[x] < rank[y]) {
                parent[xRoot] = yRoot;
            } else {
                // 此时二树的高度相等 我们让x成为y的儿子
                parent[xRoot] = yRoot;
                rank[yRoot]++;
            }

        }
        return true;
    }
}
